//
//  astar.c
//  intmap
//
//  Created by liwei on 13-11-10.
//  Copyright (c) 2013年 liwei. All rights reserved.
//

/* 
*           A*算法挑选最短路径
*/

/*
*           以下是一个5×5的数组，假设我们用[1][0]出发,目标是A点。我们发现,在途中有两种方法
*       可以达到目的地，但是往下直达的方法最短。那么找到这个最短的方法,A*算法就可以派上用了。
*       为什么要选方向朝下的点，而不是选水平方向的点呢？
*
*       0 0 0 0 0
*       1 1 1 1 1
*       1 0 0 0 1
*       1 0 0 0 1
*       A 1 1 1 1
*
*           原因不复杂，就是因为所有点中，当时我们要选的这个点和目标点之间距离最短。那么这中
*       间，路径的选择有没有发生改变呢？其实是有可能的，因为选路的过程本省就是一个pk的过程，
*       我们所能做的就是寻找当时那个离目标最近的点而已，而这个点是时刻变化的，所以最后选出来
*       的路应该是这样的。
*       
*       0 0 0 0 0
*       1 0 0 0 0
*       1 0 0 0 0
*       1 0 0 0 0
*       A 0 0 0 0
*/

/*
*           A*算法编程实现
*       首先定义一个数据结构: 二维点(Two-dimensional point)
*/

#define LENGTH_ORIGIN 1;

typedef int X;
typedef int Y;
typedef int L;
typedef int INDEX;

typedef struct _VALUE
{
    X x;
    Y y;
}POINT2D;

typedef POINT2D VALUE;

extern int find_most_nearest_neigh(VALUE data[], L length, X x, X y);

extern int check_pos_valid(X x, Y y);

extern VALUE* updata_data_for_queue(VALUE* data, L length, L* new_len);

extern void find_path(VALUE* data, VALUE origin, VALUE target);

